package com.alibaba.interview;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/**
 * @author ZhangyiA
 * @describe: 三维广搜 , 需要额外处理对称位置的转移
 * @date 2021/07/02
 */

class Point{
    public int x , y , t; // 硬性条件 t <= 5
    public Point(int x , int y , int t){
        this.x = x;
        this.y = y;
        this.t = t;
    }
}

public class Two_SymmetricalAircraft {
    // 定义四个方向
    private int[] dx = {0 , 0 , 1 , -1};
    private int[] dy = {1 , -1 , 0 , 0};
    // 起点和终点坐标
    private int sx , sy , ex , ey , n , m;
    private int[][][] v; // 记录到达每个位置所需要的消耗的对应对称飞行次数，所需要的的时间
    private char[][] grid; // 图数据

    public Two_SymmetricalAircraft(char[][] grid){
        this.grid = grid;
    }

    public void bfs(int sx , int sy){
        v[sx][sy][0] = 1;
        Queue<Point> que = new LinkedList<>();
        que.offer(new Point(sx , sy , 0));
        int nx , ny;
        while(!que.isEmpty()){
            Point point = que.poll();
            int x = point.x;  int y = point.y;  int t = point.t;
            for(int i = 0 ; i < 5 ; i ++){
                if(i == 4){
                    if(t < 5){
                        nx = n + 1 - x;
                        ny = m + 1 - y;
                        t ++;
                    }
                    else continue;
                } else {
                    nx = x + dx[i];
                    ny = y + dy[i];
                }
                if(nx >= 1 && nx <= n && ny >= 1 && ny <= m && grid[nx][ny] != '#' && v[nx][ny][t] == 0){
                    if(i == 4) {
                        v[nx][ny][t] = v[x][y][t - 1] + 1;
                    } else {
                        v[nx][ny][t] = v[x][y][t] + 1;
                    }
                    if(nx == ex && ny == ey) return;
                    que.offer(new Point(nx , ny , t));
                }
            }
        }
    }

    public int getMinTime(){
        int ans = 0;
        bfs(sx , sy);
        for(int i = 0 ; i < 6 ; i ++){
            if(v[ex][ey][i] != 0){
                ans = v[ex][ey][i] - 1;
            }
        }
        return ans;
    }

    public void init(int n , int m , int sx , int sy , int ex , int ey){
        this.v = new int[n + 1][ m + 1][6];
        this.sx = sx;  this.sy = sy;
        this.ex = ex;  this.ey = ey;
        this.n = n;  this.m = m;
    }

    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        int sx = 0 , sy = 0 , ex = 0 , ey = 0;
        int n = input.nextInt();
        int m = input.nextInt();
        char[][] grid = new char[n + 1][m + 1];
        // 数据处理阶段 , 构建数据
        for(int i = 1 ; i <= n ; i ++){
            String str = input.next();
            for(int j = 1 ; j <= m ; j ++){
                char ch = str.charAt(j - 1);
                if(ch == 'S'){
                    sx = i ;  sy = j ;
                }
                if(ch == 'E') {
                    ex = i ;  ey = j ;
                }
                grid[i][j] = str.charAt(j - 1);
            }
        }
        Two_SymmetricalAircraft symmetricalAircraft = new Two_SymmetricalAircraft(grid);
        symmetricalAircraft.init(n , m , sx , sy , ex , ey);
        System.out.println(symmetricalAircraft.getMinTime());
    }
}
